/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package intopo.evogame.partnerselection.player;

import intopo.evogame.partnerselection.*;
import intopo.evogame.partnerselection.chromosome.Chromosome;
import intopo.game.Strategy;
import intopo.partnerselection.AbstractProbabilityVector;
import java.util.Iterator;
import util.adt.Collection;

/**
 * The probability and combination vectors used in the simulation.  This class extends {@code AbstractProbabilityVector} which contains the probabilities but not the combinations.
 * A combination is a unsorted collection of partners represented by class {@code PartnerCombination}.
 *
 * <p> The vectors are fixed size and their length is determined by field {@code poolSize} of the player chromosome.  These vectors must be initialised after all dead players in a generation have been removed and newborns have been replaced.  In the first generation, they are initialised after all players have constructed and placed in their location in the population.
 *
 * @author <a href="mailto:mariano.pedro@gmail.com">Pedro Mariano</a>
 *
 * @version 1.0 __DATE__
 */
public class ProbabilityCombinationVectors<
		S extends Strategy<S>,
		C extends Chromosome<S>,
		P extends AbstractPlayer<S, C, P>
	>
	extends AbstractProbabilityVector<ProbabilityCombinationVectors.PartnerCombination<S,C,P>>
	implements java.lang.Iterable<ProbabilityCombinationVectors.PartnerCombination<S,C,P>>
{

	/**
	 * Creates a new instance of probability and combination vectors.  The chromosome is used to set the fields of parent class, namely the size of the vectors and the bits used to encode probabilities.
	 */
	public ProbabilityCombinationVectors (Chromosome<S> chromosome, Collection<P> neighbours)
	{
		super (createArray (chromosome, neighbours), 1 << (chromosome.bitsPerProbability - 1), Cache.supply);
	}
	/**
	 * The constructor of class {@code AbstractProbabilityVector} requires an array with elements.
	 * @param chromosome
	 * @param neighbours
	 * @return
	 */
	static private PartnerCombination[] createArray (Chromosome chromosome, Collection neighbours)
	{
		int size = chromosome.poolSize;
		PartnerCombination[] result = new PartnerCombination [size];
		while (size > 0) {
			size--;
			result [size] = new PartnerCombination (neighbours);
		}
		return result;
	}
	/**
	 * Return the {@code i}th partner combination and probability of the probability and combination vectors.
	 */
	final PartnerCombination<S, C, P> getCombination (int i)
	{
		return (PartnerCombination<S, C, P>) this.getSlot(i);
	}

		/**
	 * Return the index of a partner combination randomly selected using the
	 * probability vector.  A binary search is used to find the smallest
	 * partial sum not lower than a random {@code int}.
	 *
	 * <p> The probability vector contains partial sums. Therefore,
	 * selecting a partner has time complexity {@code log(n)}, however
	 * updating the vector has time complexity {@code O(n)}, where {@code n}
	 * is the number of combinations.  As games are played and if there are
	 * cooperative combinations, there are fewer probability vector updates.
	 *
	 * <p> The pseudo-random number generator is stored in class {@code
	 * Cache}.  This class contains global constant values that are
	 * initialised in runtime after reading a configuration file.
	 */
	final protected int randomCombination ()
	{
		return this.randomCombination(Cache.supply);
	}

	/**
	 * After removal of dead players, check invalid combinations.
	 * After dead players have been removed and new born have been inserted,
	 * update combination vector.  Probabilities remain unchanged.
	 *
	 * <p> Updating the combination vector is done in two passes.  We avoid
	 * the risk of two instances having the same hash key.
	 *
	 * @see #updateCombinations()
	 */
	final void checkInvalidCombinations ()
	{
		for (int i = this.length1; i >= 0; i--) {
			PartnerCombination<S, C, P> pc = this.getCombination (i);
			pc.valid = pc.combination.valid ();
		}
		for (int i = this.length1; i >= 0; i--) {
			PartnerCombination<S, C, P> pc = this.getCombination (i);
			if (!pc.valid) {
				try {
					this.replaceCombination (i);
					pc.valid = true;
				}
				catch (java.lang.IllegalArgumentException e) {
					// the set of candidate partners does not have sufficient elements
				}
			}
		}
	}

	/**
	 * Replace combination in slot {@code combinationIndex} of the
	 * combination vector with a randomly selected combination.  This is
	 * done when a combination from the previous round is invalid or when it
	 * is replaced by the combination vector update policy.
	 */
	final void replaceCombination (int combinationIndex)
	{
		// select a random combination different from those in the combination vector
		PartnerCombination<S, C, P> pc = this.getCombination (combinationIndex);
		// repetead combinations
		do {
			try {
				pc.combination.newSubset (Cache.supply);
			}
			catch (java.lang.RuntimeException e) {
				throw e;
			}
		} while (!newCombination (pc, 0, combinationIndex - 1)
			|| !newCombination (pc, combinationIndex + 1, this.length1));
	}

	/**
	 * Return {@code true} if the given combination is different from those
	 * in the combination vector in the given range.
	 *
	 * @param from Range lower bound.
	 * @param to Range upper bound.  This slot is not included in the search.
	 */
	private boolean newCombination (PartnerCombination combination, int from, int to)
	{
		if (AbstractPlayer.Parameters.distinctCombinations) {
			for (int i = from; i <= to; i++) {
				if (this.getCombination (i).valid
					&& this.getCombination (i).equals (combination)) {
					return false;
				}
			}
		}
		return true;
	}

	@Override
	public Iterator<ProbabilityCombinationVectors.PartnerCombination<S,C,P>> iterator ()
	{
		return new PCIterator ();
	}
	/**
	 * Represents an element from the probability and combination vectors.
	 *
	 * <p> The probability vector contains partial sums. Therefore,
	 * selecting a partner has time complexity {@code log(n)}, however
	 * updating the vector has time complexity {@code O(n)}, where {@code n}
	 * is the number of combinations.  As games are played and if there are
	 * cooperative combinations, there are fewer probability vector updates.
	 */
	static public class PartnerCombination<
			S extends Strategy<S>,
			C extends Chromosome<S>,
			P extends AbstractPlayer<S, C, P>
		>
		 extends intopo.partnerselection.AbstractProbabilityVector.Slot
	{
		/**
		 * The combination of this element of the combination vector.
		 */
		final Collection.Subset<P> combination;

		/**
		 * Indicates if this element is valid or not. Removal of neighbours
		 * due to death may invalidate existing combinations in the vector.
		 */
		boolean valid;

		/**
		 * Construct a new element of the probability and combination vectors.
		 */
		PartnerCombination (Collection<P> candidatePartners)
		{
			this.combination = candidatePartners.subset (Cache.numberPartners, Cache.supply);
			this.valid = false;
		}
		public String toString ()
		{
			return String.format ("%b %s", this.valid, this.combination.toString ());
		}
	}
	private class PCIterator
	  implements Iterator<ProbabilityCombinationVectors.PartnerCombination<S,C,P>>
	{
		private int index = length1;
		@Override
		public boolean hasNext ()
		{
			return index >= 0;
		}

		@Override
		public PartnerCombination<S, C, P> next ()
		{
			PartnerCombination<S, C, P> result = getCombination (index);
			index--;
			return result;
		}

		@Override
		public void remove ()
		{
			throw new UnsupportedOperationException("Not supported yet.");
		}

	}
}



// Local Variables:
// mode: java
// mode: flyspell-prog
// ispell-local-dictionary: "british"
// End:
